\subsection{Behavioral changes}
\label{sec:behavioral}
In this section, we study non-cooperative games with
connection-altering interventions (a.k.a. behavior changes). As
before, locality is parameterized by $d$. Among all possible models
for behavior changes, we focus on the 1-sided and 2-sided model
(defined in Section \ref{sec:intervention-framework}). We are
interested in studying the following questions. How are the properties
of NE affected by the behavior change parameter $p_b$ and the vaccine
efficacy? Are there threshold phenomena involving these parameters, so
that an increase in $p_b$ beyond the threshold value $p^*_b$ changes
the dynamic significantly? How does price of anarchy change?
Furthermore, what kind of nodes tend to choose to get vaccinated? Can
we achieve equilibria that are close to the social optimum through a
public policy that provides certain amount of vaccines (subject to a
budget) and provides appropriate local and global information to
individual players?

\subsubsection{Our results}
As a first step, we will focus on symmetric strategies, in which the
intervention strategy $a_v$ and $p_b$ are the same for all nodes. We
want to understand how diffusion dynamics (e.g. the average outbreak
size, and the time to peak), and the total utility as defined in
Equation \ref{eqn:cost} vary as a function of $a_v$ and
$p_b$. Furthermore in order to answer the public policy issues would
require understanding the interplay between the locality parameter $d$
and the behavior change parameter $p_b$, which may depend
significantly on the vaccine efficacy and could be very different in
the 1-sided and 2-sided models.

In our preliminary work, we have studied the social cost and
differences between 1-sided and 2-sided models. We assume that
interventions failed with probability $p_f$. Through simulations, we
found that both forms of behavior changes would lead to perverse
outcomes across a wide range of contact networks. 1-sided behavior
change leads to perverse outcomes at low levels of intervention, in
which the average outbreak increases with $a_v$, up to a point, as
shown in Figure \ref{fig:mh}. 2-sided behavior change leads to
perverse outcomes at high levels of intervention, in which the average
outbreak size starts increasing beyond a threshold value of $a_v$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=3in]{figures/pa_1end_06_02_09.jpg}
\includegraphics[width=3in]{figures/pa_2end_08_01.jpg}
\caption{ Variation in the giant component size with $a_{v}$ for the
  1-sided and 2-sided models of behavior changes in scale-free graphs.
  On the left is the comparison of uniform vaccination with two kinds
  of degree-preferred vaccination policies in the 1-sided model, for
  $p = 0.2$, $p_b = 0.9$, $p_f = 0.4$.  On the right are the curves
  for different values of behavior change probability $p_b$ in the
  2-sided model, for $p = 0.1$, $p_f = 0.2$.  The giant component size
  is a good estimate for the expected epidemic size.}
\label{fig:mh}
\end{center}
\end{figure}

To answer those questions in which we are interested, a significant
fraction of our efforts will be devoted to developing analytical
tools. Our initial foray has been on Erd\"os-R\'enyi networks that
have formed the basic underlying network in traditional SIR models.  A
major technical hurdle we face is that when the behavioral models are
incorporated, even homogeneous Erd\"os-R\'enyi networks are
transformed to heterogeneous networks.  One powerful tool for
analyzing percolation on heterogeneous networks is that of {\em
  multi-type branching processes}.  We plan to build on recent results
of S\"oderberg~\cite{soderberg+inhomo02} and Bollob\'{a}s et
al~\cite{bollobas+inhomo} in this regard.

Consider a random graph model denoted by
$\mathcal{G}(N,K,\textbf{r},\textbf{c})$, where (i) $K$ is a positive
integer, (ii) $\textbf{r}=\{r_1,\ldots,r_K\}$ is a probability vector,
(iii) $\textbf{c}=(c_{ij})$ is a $K\times K$ matrix, (iv) each node
$j=1,\ldots,N$, is assigned a type $i\in\{1,\ldots,K\}$ with
probability $r_i$, and (v) each pair of nodes $i, j$ are connected by
an edge with probability
$p(i,j)=c_{ij}/N$. S\"{o}derberg~\cite{soderberg+inhomo02} and
Bollob\'{a}s et al.~\cite{bollobas+inhomo} establish the following:
(i) if the eigenvalues of the matrix $\{c_{ij}r_j\}$ are all less than
1, it is sub-critical (i.e., has no giant component), and (ii) if some
eigenvalue is larger than 1, it is super-critical (i.e., has a giant
component) with asymptotically $r_i(1-f_i)N$ nodes of type $i$, where
$f_i$ satisfies the coupled set of equations: $f_i = exp\left(\sum_j
c_{ij}r_j(f_j-1)\right)$. Using the above threshold result, we have
given a rigorous proofs for the diverse non-monotonicity phenomena of
Figure \ref{fig:mh} in the case of Erd\"os-R\'enyi random graphs.

Empirically, we have observed that the phenomenon is widespread across
a range of networks including preferential attachment networks.  We
are also applying traditional percolation theory techniques to the
class of locally-finite infinite
networks~\cite{bollobas:percolationBook} as a proof of concept.  Our
findings have implications for public policy and the distribution of
vaccines.  More surprisingly we observe that targeted vaccination can
be strictly worse than random vaccination for the same level of
vaccine coverage and this phenomenon occurs both for one-sided as well
as two-sided risk behavior change (as shown in Figure \ref{fig:mh}).
Given the prior work on targeting vaccine distributions this finding
flies in the face of intuition that expects that vaccinating highly
connected individuals would always confer greater benefits.

\subsubsection{Proposed research}
We propose to study the following open problems.

\begin{enumerate}
\item We have a rigorous proof for the existence of non-monotonicity
  in Erd\"os-R\'enyi random graphs. Can we capture more detailed
  features of the non-monotonicity curves shown in Figure \ref{fig:mh}
  (e.g. do the curves have unique maximum/minimum point)?.
\item Extend rigorous proofs of Erd\"os-R\'enyi random graphs to more
  general networks, like preferential attachment graphs or
  locally-finite infinite graphs, to explain the diverse
  non-monotonicity phenomena shown in Figure \ref{fig:mh}. \junk{If we
    apply the same S\"oderberg techniques, it requires solving the
    coupled equations and bounding the fixed points $f_i$ in a more
    general setting, and appears to be significantly more
    challenging. We hope that generating function techniques (e.g.,
    MacMahon Master Theorem~\cite[Chapter~1]{goulden+j:book}) would
    help us compute useful bounds for relevant network families.}
\item In the simulation, we observe targeted vaccination can be
  strictly worse than random vaccination for some levels of vaccine
  coverage. Can we mathematically prove this?
\item Develop simulations to cover more families of graphs to confirm
  our findings.
\end{enumerate}
